package com.YOUtils.DataStucture;

import com.YOUtils.Base.Str.YoStringUtils;
import com.yum.Iterator.List.YArrayList.YArrayList;
import com.yum.Iterator.List.YList;

/**
 * Created on 2023/6/25
 * 字典树(Trie)
 * @Time 11:12
 * @Program YOUilt
 * @Author YoHaNe/XiaoShuai
 */
public class Trie {


    private final TrieNode root;

    public Trie(){
        this(null);
    }

    public Trie(String str){
        root = new TrieNode();
        insertStr(str);
    }

    public void insertStr(String str){
        if(YoStringUtils.isEmpty(str))
            return;
        TrieNode node = root;
        for(char c : str.toCharArray()){
            if(node.next[c - 'a'] == null)
                node.next[c - 'a'] = new TrieNode();
            node = node.next[c - 'a'];
        }
        node.isWord = true;
    }

    public boolean search(String word){
        TrieNode node = root;
        for(char c : word.toCharArray()){
            int index = c - 'a';
            if(node.next[index] == null)
                return false;
            node = node.next[index];
        }
        return node.isWord;
    }

//    public YList<String> like(String word){
//        TrieNode node = root;
//        YList<String> result = new YArrayList<>();
//        for(char c : word.toCharArray()){
//            int index = c - 'a';
//            if(node.next[index] == null)
//                return null;
//            node = node.next[index];
//        }
//        if(node.isWord){
//            result.add(word);
//
//        }
//    }




    static class TrieNode{
        boolean isWord;
        TrieNode[] next;

        public TrieNode() {
            this.isWord = false;
            next = new TrieNode[26];
        }

    }

}
